/*
 * Question: Suppose that a binary tree is stored in
 * two arrays, namely L[1..n] and R[1..n]. L[i] and
 * R[i] indicate the left child and right child of i,
 * respectively. try to propose an algorithm to determine
 * whether or not node u is the descendent of node v.
 */

#include <iostream>
#include <fstream>
#include <stack>
#include "iofile.h"
#include "sqlist.h"
using namespace std;

class sqlist : public _sqlist<int> {};
sqlist L, R;

/*
 * Lunch a BFS to travel the subtree of node v.
 * If there is a node is indentical to node u in our
 * search path, u is the descendent of v certainly.
 * Otherwise not.
 */
int is_descendent(int u, int v)
{
    stack<int> s;
    int n;

    if (u == v) return false;

    s.push(v);
    while (!s.empty()) {
        n = s.top();
        s.pop();
        if (n == u) return 1;
        if (L.elem[n]) s.push(L.elem[n]);
        if (R.elem[n]) s.push(R.elem[n]);
    }
    return 0;
}

int main()
{
    int u, v;

    open_input("chap06/ex33.txt");
    sqlist_create<sqlist, int>(L);
    sqlist_create<sqlist, int>(R);
    cout << "ancestor = ";
    cin >> v;
    cout << "descendent = ";
    cin >> u;
    if (is_descendent(u, v))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    sqlist_destory(L);
    sqlist_destory(R);
    close_input();
    return 0;
}
